import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author 雷明浩
 * @date 2025/7/3 9:56
 */
public class ThreeSum {
    // 三数之和
    // https://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        // write code here
        int len = num.length;
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if (len < 3) {
            return ret;
        }
        Arrays.sort(num);
        if (num[0] > 0 || num[len-1] < 0) {
            return ret;
        }
        for (int i = 0; i < len-2; i++) {
            if (num[i] > 0) {
                break;
            }
            if (i > 0 && num[i] == num[i-1]) {
                continue;
            }
            int j = i + 1;
            int k = len-1;
            int target = -num[i];
            while (j < k) {
                int sum = num[j] + num[k];
                if (sum == target) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(num[i]);
                    list.add(num[j]);
                    list.add(num[k]);
                    ret.add(list);
                    j++;
                    k--;
                } else if (sum < target) {
                    j++;
                } else {
                    k--;
                }
                while (j != i + 1 && j < k && num[j] == num[j-1]) {
                    j++;
                }
                while (k < len-1 && j < k && num[k] == num[k+1]) {
                    k--;
                }
            }
        }
        return ret;
    }
}